"""
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
"""
from typing import Optional
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head = ListNode(0)
        p = head#用于合并的链表
        a = list1 #指向第一个链表的指针
        b = list2 #只想第二个链表的指针
        while a and b:
            if a.val <= b.val:
                p.next = ListNode(a.val)
                a = a.next
                p = p.next
            else:
                p.next= ListNode(b.val)
                b = b.next
                p = p.next
        if a:
            p.next = a
        if b:
            p.next = b
        return head.next

